class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        srand(time(NULL));
        qsort(nums,0,nums.size()-1);
        return nums;
    }
    void qsort(vector<int>& nums,int left,int right)
    {
        if(left>=right) return;
        int key = randkey(nums,left,right);
        int i = left,l=left-1,r=right+1;
        while(i<r)
        {
            if(nums[i]<key) swap(nums[++l],nums[i++]);
            else if(nums[i]==key) i++;
            else swap(nums[--r],nums[i]);
        }
        qsort(nums,left,l);
        qsort(nums,r,right);
    }
    int randkey(vector<int>& nums,int left,int right){
        int r  = rand();
        return nums[r%(right-left + 1)+ left];
        
    }
};
